#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const int N=1e5+5;
#define INF 0x3f3f3f3f;
typedef long long int ll;
#define close(); std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
//----------------------------------------------------------------------------//
int bi[N],xi[N];//bi花费,xi为多少人抱团
ll f[N];//f[i]表示减少到i个人时消耗的最小能量
void solve()
{
	int n,m;
	cin>>n>>m;//n人数,m指令个数
	for(int i=1;i<=m;i++) cin>>bi[i]>>xi[i];//bi花费,xi为多少人抱团
	
	
	f[n]=0;//还剩n人时指令需要0次,初始化
	for(int i=n;i>=1;i--)//遍历指令,用已知更新未知从后往前遍历
	{
		for(int j=1;j<=m;j++)//每次循环指令
		{
			if(xi[j]>i) continue;
			else
			{
				ll t=i-(ll)i%xi[j];
				f[t]=min(f[t],f[i]+bi[j]);
			}
		}
	}

	ll mx=0x3f3f3f3f3f3f3f3f;
	for(int i=1;i<=n;i++)//顺序遍历,出现的就是最小的人数,也是最小操作数
	{
		if(f[i]!=mx)
		{
			cout<<f[i]<<'\n';
			return;
		}
	}

	cout<<-1<<'\n';


	
}

int main()
{
	close();
	memset(f, 0x3f, sizeof f);
	solve();
	return 0;
}